package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-27 15:03
 **/
public class JianZhiOffer53 {

    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        //记录target出现的次数
        int count = 0;
        //记录target第一次出现的索引
        int index = 0;
        while (low <= high) {
            int avg = (low + high) >> 1;
            if (nums[avg] == target) {
                index = avg;
                count++;
                break;
            } else if (nums[avg] > target) {
                high = avg - 1;
            } else {
                low = avg + 1;
            }
        }
        //count为0说明target不存在，直接返回
        if (count == 0) {
            return 0;
        }
        //复制一份index的值，方便向左右两边蔓延寻找target
        int index2 = index;
        while (index < nums.length - 1 && nums[++index] == target) {
            count++;
        }
        while (index2 > 0 && nums[--index2] == target) {
            count++;
        }
        return count;


    }

}
